package org.leetcode.middle.leetcode92;


import java.util.List;
import java.util.LongSummaryStatistics;

public class Solution
{
    public ListNode reverseBetween(ListNode head, int left, int right)
    {
        if (head==null || head.next==null || left==right)
        {
            return head ;
        }

        ListNode before = null;
        ListNode after  = null;
        ListNode temp   = head;
        int index =0;

        while (head!=null)
        {
            index++;
            if (index==left-1)
            {
                before = head;
                temp   = head.next;
                head   = head.next;
                index++;
                before.next=null;

            }else if (index==right)
            {
                after = head.next;
                head.next=null;
            }

            head=head.next;
        }

        ListNode reverse = reverse(temp);

        ListNode lastNode = findLastNode(reverse);

        if (before!=null && after!=null)
        {
            before.next=reverse;
            lastNode.next=after;
        }else if (before==null && after!=null)
        {
            lastNode.next=after;
            return reverse;
        }else if (before!=null && after==null)
        {
            before.next=reverse;
        }else {
            return reverse;
        }


        return before;


    }

    private ListNode findLastNode(ListNode listNode)
    {
        if (listNode==null)
        {
            return listNode;
        }

        while (listNode.next!=null)
        {
            listNode=listNode.next;
        }

        return listNode;
    }

    private ListNode reverse(ListNode listNode)
    {
        ListNode prev = null;
        ListNode temp = listNode;

        while (listNode!=null)
        {
            temp = temp.next;
            listNode.next=prev;
            prev=listNode;
            listNode=temp;
        }

        return prev;
    }


    public ListNode reverseBetween2(ListNode head, int left, int right) {
        // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;

        ListNode pre = dummyNode;
        // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        // 建议写在 for 循环里，语义清晰
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        ListNode rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode.next;
        }

        // 第 3 步：切断出一个子链表（截取链表）
        ListNode leftNode = pre.next;
        ListNode curr = rightNode.next;

        // 注意：切断链接
        pre.next = null;
        rightNode.next = null;

        // 第 4 步：同第 206 题，反转链表的子区间
        reverseLinkedList(leftNode);

        // 第 5 步：接回到原来的链表中
        pre.next = rightNode;
        leftNode.next = curr;
        return dummyNode.next;
    }

    private void reverseLinkedList(ListNode head) {
        // 也可以使用递归反转一个链表
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }



    public ListNode reverseBetween3(ListNode head, int left, int right){
        /**
         * leftNode:反转链表的起始的前一个节点
         * rightNode:反转链表的结尾的后一个节点
         * reverseStart:反转链表的头结点，反转之后变成了尾结点
         * reverseEnd:反转链表的尾结点，反转之后变成了头结点
         */
       ListNode dummyNode = new ListNode(0);
       dummyNode.next=head;

       ListNode leftNode = dummyNode;

        for (int i = 0; i < left-1; i++) {
            leftNode=leftNode.next;
        }

        ListNode reverseStart=leftNode.next;

        ListNode reverseEnd = leftNode;
        for (int i = 0; i < right-left+1; i++)
        {
            reverseEnd=reverseEnd.next;
        }

        ListNode rightNode = reverseEnd.next;

        leftNode.next=null;
        reverseEnd.next=null;

        reverseLinkedList(reverseStart);

        leftNode.next=reverseEnd;
        reverseStart.next=rightNode;

        return dummyNode.next;

    }

    public ListNode reverseBetween4(ListNode head,int left,int right)
    {
        ListNode dummyNode = new ListNode(0);

        dummyNode.next=head;

        ListNode pre = dummyNode;

        for (int i = 0; i < left-1; i++) {
            pre=pre.next;
        }

        ListNode cur=pre.next ;
        ListNode next;


        for (int i = 0; i < right-left; i++) {
            next=cur.next;

            cur.next=next.next;
            next.next=pre.next;
            pre.next=next;

        }

        return dummyNode.next;

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
//        ListNode listNode = new ListNode(1,new ListNode(2,new ListNode(3,null)));
        ListNode resultList = solution.reverseBetween4(listNode, 2, 4);
    }

}
